package offer;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * @Author Elephas
 * @Date 2022/1/18
 **/
public class LengthOfLongestSubstring {
    /*
        解法一： 对其子串依次求长度，暴力破解
     */
    public int lengthOfLongestSubstring(String s){
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            int len = lengthOfSubstring(s.substring(i));
            if(len > ans){
                ans = len;
            }
        }
        return ans;
    }
    public int lengthOfSubstring(String s){
        Set<Character> set = new HashSet<>();
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if(!set.contains(s.charAt(i))){
                ans++;
                set.add(s.charAt(i));
            }else{
                break;
            }
        }
        return ans;
    }
    /*
        解法二：考虑优化解法，使用一个队列，和一个集合，时刻记录队列中元素最多时数量
     */
    public int lengthOfLongestSubstring2(String s) {
        int maxLen = 0, len = 0;
        Set<Character> characterSet = new HashSet<>();
        Queue<Character> characterQueue = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (characterSet.contains(s.charAt(i))) {
                // 从头删除重复元素
                while (true) {
                    char temp = characterQueue.remove();
                    characterSet.remove(temp);
                    len--;
                    if (temp == s.charAt(i))
                        break;
                }
            }
            characterSet.add(s.charAt(i));
            characterQueue.offer(s.charAt(i));
            len++;
            if (maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }
    /*
        不使用队列实现解法2
     */
    public int lengthOfLongestSubstring3(String s) {
        int maxLen = 0, left = -1;
        Set<Character> characterSet = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            if(characterSet.contains(s.charAt(i))){
                while(true){
                    left++;
                    char temp = s.charAt(left);
                    characterSet.remove(temp);
                    if(temp == s.charAt(i)){
                        break;
                    }
                }
            }
            characterSet.add(s.charAt(i));
            if(maxLen < i - left){
                maxLen = i - left;
            }
        }
        return maxLen;
    }
}
